Exercise (Week 5)

1. Priority Queues and State (9 Marks)

DUE: Thu 14 July 09:10:00

1 Priority Queues and State (9 Marks)

CSEStack

Download the exercise tarball and extract it to a directory in your home directory at CSE. This tarball contains a file, called Ex04.hs, wherein you will do all of your programming. Other files include Priority.hs and Size.hs. Do not modify the other files.

To test your code, run the following shell commands to open a GHCi session:

$ 3141
newclass starting new subshell for class COMP3141...
$ cabal repl
Resolving dependencies...
Configuring Ex04-1.0...
Preprocessing executable 'Ex04' for Ex04-1.0..
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Ex04          (Ex04.hs, interpreted)
Ok, one module loaded.
*Ex04>

Note that you will only need to submit Ex04.hs, so only make changes to that file.

Download the exercise tarball and extract it to a directory on your local machine. This tarball contains a file, called Ex04.hs, wherein you will do all of your programming. Other files include Priority.hs and Size.hs. Do not modify the other files. To test your code, run the following shell commands to open a GHCi session:

$ stack repl
Configuring GHCi with the following packages: Ex04
Using main module: 1. Package 'Ex04' component exe:Ex04 ...
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Ex04          (Ex04.hs, interpreted)
Ok, one module loaded.
*Ex04>

Note that you will only need to submit Ex04.hs, so only make changes to that file.

A QueueTree a is a (possibly empty) binary tree data structure obeying the following well-formedness conditions.

Condition 1

Each leaf of the tree stores the following data:

A value of type a.
A value of type Priority (data Priority = Priority Integer), storing a positive integer called the priority of the element (object of type a) stored in the leaf. We sometimes refer to this as the priority of the leaf.
A value of type Size (data Size = Size Integer) counting the number of elements (objects of type a) stored in the leaf.

Condition 2

Each non-leaf node of the tree stores the following data:

A value of type Priority, storing the largest priority of any leaf that occurs in the subtrees of the node.
A value of type Size, counting the total number of non-empty leaves in the subtrees of the node.
Two subtrees of type QueueTree a (the left and right subtree).

Familiarize yourself with the data type declaration for QueueTree a given in Ex04.hs. Read the implementations of the data structures Size and Priority. Pay attention to the ~Semigroup and Monoid instances of each type.

The following tree of type QueueTree Char is well-formed according to the conditions above:

Node (Size 3,Priority 7)
  ( Node (Size 2,Priority 7)
      (Leaf (Size 1,Priority 7) 'b')
      (Leaf (Size 1,Priority 5) 'c')
  )
  (Leaf (Size 1,Priority 3) 'a')

However, the tree below is not well-formed: the top level Node has the incorrect Size, while the second level node has the incorrect priority.

Node (Size 2,Priority 7)
  ( Node (Size 2,Priority 5)
      (Leaf (Size 1,Priority 7) 'b')
      (Leaf (Size 1,Priority 5) 'c')
  )
  (Leaf (Size 1,Priority 3) 'a')

We say that a QueueTree a data structure is balanced if the following condition holds at each of its node: the (absolute) difference between the size of the left subtree and the size of the right subtree is at most one.

Balanced QueueTree a data structures allow us to implement asymptotically efficient priority queues. The priority queue developed in this exercise supports insertions and dequeue operations in logarithmic time: with a small change to the data structure, the dequeue operation could be improved to constant time.

1.1 Task 1 (3 marks)

Your first task is to define a function `wf :: QueueTree a -> Bool` that tests whether the given QueueTree is well-formed according to the criteria above.

Then, define two smart constructors,

leaf :: Priority -> a -> QueueTree a
node :: QueueTree a -> QueueTree a -> QueueTree a

which behave exactly like their counterparts Leaf and Node, but automatically calculate the NodeInfo values so as to maintain the invariants. I.e., given well-formed inputs, these constructors should always produce well-formed output.

Keep in mind that being balanced is not part of the well-formedness criterion!

1.2 Task 2 (3 marks)

A priority queue is a data structure that behaves similarly to an ordinary queue (first-in first-out queue), except that each element has an associated integer priority value. The priority values of the elements determine the order in which elements are removed (popped, dequeued) from the priority queue: the ones with the highest priority are removed first.

Priority queues traditionally support two operations:

pop: Remove the element with the highest priority from the priority queue (yielding a new queue) and return the removed element (or fail if the queue is empty).
insert: add an element to the queue with the given priority

which will be represented by the following type signatures:

pop :: QueueTree a -> (QueueTree a, Maybe a)
insert :: Priority -> a -> QueueTree a -> QueueTree a

Your first task is to implement these two functions. Both functions should preserve preserve well-formedness of the QueueTree structure. Moreover, the insert function should also preserve balancedness, in the sense that if the input tree is balanced, the output tree should be balanced as well! If two elements have the same priority, you are free to remove them in pop in any order you choose.

Your second task is to implement a function fromList which takes a list of (Priority, element) pairs, and converts them into a balanced QueueTree with the same elements.

1.3 Task 3 (3 marks)

Functions such as pop and insert can be thought of as funtions that manipulate the state of a QueueTree.

Accordingly, your first task is to implement versions of pop and insert that work with the State type in Haskell's standard mtl library (Control.Monad.State), with the following signatures:

pop' :: State (QueueTree a) (Maybe a)
insert' :: Priority -> a -> State (QueueTree a) ()

Your second task is to implement the peek' operation, which returns the same output as pop', but leaves the state of the `QueueTree` unchanged.

Hints:

You may want to revisit the slides of Lecture 5, which explain how this type corresponds to the State

type and bindS function we defined during that lecture.

The Ex04.hs file contains some examples of computations involving State.
To get comfortable with Haskell's State type, you can try to re-develop the material of Lecture 5 (which used our own user-defined State type) using Control.Monad.State. This is one of the most important exercises of the whole term, so don't give up if things don't go smoothly on your first try! Understanding this material is crucial for doing well in the rest of the term.

1.4 Remarks

We are in Week 5, halfway through COMP3141, and flexibility week is coming up. If you feel that you're falling behind, now is your chance to catch up! The second half of the course is devoted to monads, and requires you to be comfortable with all aspects of Haskell covered in the course so far.

If you feel that your knowledge has gaps, this is the time to rewatch the lectures, ask questions in the course forum, and read the Haskell resources suggested in the course outline! One of these resources is Learn You a Haskell, a freely available textbook: chapters 1 to 8 cover almost all of the Haskell programming knowledge that we've touched upon in this course.

Similarly, if you encountered difficulties with the previous assignments, now is the time to revisit and practice them. You should try to develop independent solutions, and refer to the practical lectures if you get stuck.

1.5 Submission instructions

You can submit your exercise by typing:

$ give cs3141 ex04 Ex04.hs

on a CSE terminal, or by using the give web interface. Your file must be named Ex04.hs (case-sensitive!).

A dry-run test will partially autotest your solution at submission time. To get full marks, you will need to perform further testing yourself.